/*
Copyright (c) 2008, Mike Gashler

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/

#include <stdio.h>
#include "GHashTable.h"
#include <wchar.h>
#include <stdlib.h>
#ifdef WIN32
#	include <malloc.h>
#endif

struct HashBucket
{
	HashBucket* pPrev;
	HashBucket* pNext;
	const char* pKey;
	const void* pValue;
};

GHashTableBase::GHashTableBase(int nInitialBucketCount)
{
	m_nBucketCount = 0;
	m_pBuckets = NULL;
	m_nCount = 0;
	m_nModCount = 0;
	_Resize(nInitialBucketCount);
}

GHashTableBase::~GHashTableBase()
{
	delete[] m_pBuckets;
}

inline bool IsObviousNonPrime(int n)
{
	if((n % 3) == 0)
		return true;
	if((n % 5) == 0)
		return true;
	if((n % 7) == 0 && n != 7)
		return true;
	if((n % 11) == 0 && n != 11)
		return true;
	if((n % 13) == 0 && n != 13)
		return true;
	if((n % 17) == 0 && n != 17)
		return true;
	return false;
}

void GHashTableBase::_Resize(int nNewSize)
{
	// Find a good size
	if(nNewSize < m_nCount * 3)
		nNewSize = m_nCount * 3;
	if(nNewSize < 7)
		nNewSize = 7;
	if((nNewSize & 1) == 0)
		nNewSize++;
	while(IsObviousNonPrime(nNewSize))
		nNewSize += 2;

	// Allocate the new buckets
	struct HashBucket* pOldBuckets = m_pBuckets;
	m_pBuckets = new struct HashBucket[nNewSize];
	int nOldCount = m_nBucketCount;
	m_nBucketCount = nNewSize;
	m_nCount = 0;

	// Init the new buckets
	m_pBuckets[0].pPrev = NULL;
	m_pBuckets[0].pNext = &m_pBuckets[1];
	m_pBuckets[0].pKey = NULL;
	int n;
	int nNewSizeMinusOne = nNewSize - 1;
	for(n = 1; n < nNewSizeMinusOne; n++)
	{
		m_pBuckets[n].pPrev = &m_pBuckets[n - 1];
		m_pBuckets[n].pNext = &m_pBuckets[n + 1];
		m_pBuckets[n].pKey = NULL;
	}
	m_pBuckets[nNewSizeMinusOne].pPrev = &m_pBuckets[nNewSizeMinusOne - 1];
	m_pBuckets[nNewSizeMinusOne].pNext = NULL;
	m_pBuckets[nNewSizeMinusOne].pKey = NULL;
	m_pFirstEmpty = &m_pBuckets[0];

	// Copy the old data
	for(n = 0; n < nOldCount; n++)
	{
		if(pOldBuckets[n].pKey)
			_Add(pOldBuckets[n].pKey, pOldBuckets[n].pValue);
	}

	// delete the old buckets
	delete[] pOldBuckets;
	m_nModCount++;
}

void GHashTableBase::_Add(const char* pKey, const void* pValue)
{
	// Check inputs
	if(!pKey)
		ThrowError("Hash table key can't be NULL");

	// Resize if necessary
	if(m_nCount * 2 > m_nBucketCount)
		_Resize(m_nBucketCount * 2);
	else
		m_nModCount++;

	// Determine which bucket
	unsigned int nPos = Hash(pKey, m_nBucketCount);
	if(nPos >= (unsigned int)m_nBucketCount)
		ThrowError("Hash out of range");

	// Insert it
	m_nCount++;
	if(m_pBuckets[nPos].pKey)
	{
		// The bucket is occupied, so either boot them out or rent a place yourself
		if(m_pBuckets[nPos].pPrev)
		{
			// The bucket is being rented by someone else.  Boot them out to the next available empty spot.
			struct HashBucket* pRenter = m_pFirstEmpty;
			m_pFirstEmpty = pRenter->pNext;
			m_pFirstEmpty->pPrev = NULL;
			*pRenter = m_pBuckets[nPos];
			pRenter->pPrev->pNext = pRenter;
			if(pRenter->pNext)
				pRenter->pNext->pPrev = pRenter;
		
			// Move in
			m_pBuckets[nPos].pPrev = NULL;
			m_pBuckets[nPos].pNext = NULL;
			m_pBuckets[nPos].pKey = pKey;
			m_pBuckets[nPos].pValue = pValue;
		}
		else
		{
			// The bucket is already owned, so just rent the first available empty spot.
			struct HashBucket* pNewBucket = m_pFirstEmpty;
			m_pFirstEmpty = pNewBucket->pNext;
			m_pFirstEmpty->pPrev = NULL;
			pNewBucket->pKey = pKey;
			pNewBucket->pValue = pValue;
			pNewBucket->pNext = m_pBuckets[nPos].pNext;
			pNewBucket->pPrev = &m_pBuckets[nPos];
			m_pBuckets[nPos].pNext = pNewBucket;
			if(pNewBucket->pNext)
				pNewBucket->pNext->pPrev = pNewBucket;
		}
	}
	else
	{
		// The bucket is empty.  Move in.
		if(m_pBuckets[nPos].pPrev)
			m_pBuckets[nPos].pPrev->pNext = m_pBuckets[nPos].pNext;
		else
		{
			m_pFirstEmpty = m_pBuckets[nPos].pNext;
		}
		if(m_pBuckets[nPos].pNext)
			m_pBuckets[nPos].pNext->pPrev = m_pBuckets[nPos].pPrev;
		m_pBuckets[nPos].pPrev = NULL;
		m_pBuckets[nPos].pNext = NULL;
		m_pBuckets[nPos].pKey = pKey;
		m_pBuckets[nPos].pValue = pValue;
	}
}

bool GHashTableBase::_Get(const char* pKey, void** pOutValue)
{
	unsigned int nPos = Hash(pKey, m_nBucketCount);
	if(nPos >= (unsigned int)m_nBucketCount)
		ThrowError("Hash out of range");
	if(!m_pBuckets[nPos].pKey || m_pBuckets[nPos].pPrev)
		return false;
	struct HashBucket* pBucket;
	for(pBucket = &m_pBuckets[nPos]; pBucket; pBucket = pBucket->pNext)
	{
		if(AreKeysEqual(pBucket->pKey, pKey))
		{
			*pOutValue = (void*)pBucket->pValue;
			return true;
		}
	}
	return false;
}

int GHashTableBase::_Count(const char* pKey)
{
	unsigned int nPos = Hash(pKey, m_nBucketCount);
	if(!m_pBuckets[nPos].pKey || m_pBuckets[nPos].pPrev)
		return 0;
	int nCount = 0;
	struct HashBucket* pBucket;
	for(pBucket = &m_pBuckets[nPos]; pBucket; pBucket = pBucket->pNext)
	{
		if(AreKeysEqual(pBucket->pKey, pKey))
			nCount++;
	}
	return nCount;
}

void GHashTableBase::_Remove(const char* pKey)
{
	unsigned int nPos = Hash(pKey, m_nBucketCount);
	if(nPos >= (unsigned int)m_nBucketCount)
		ThrowError("Hash out of range");
	if(!m_pBuckets[nPos].pKey || m_pBuckets[nPos].pPrev)
		return;
	struct HashBucket* pBucket;
	for(pBucket = &m_pBuckets[nPos]; pBucket; pBucket = pBucket->pNext)
	{
		if(AreKeysEqual(pBucket->pKey, pKey))
		{
			if(pBucket->pPrev)
			{
				// It's just a renter, so unlink it and delete the bucket
				pBucket->pPrev->pNext = pBucket->pNext;
				if(pBucket->pNext)
					pBucket->pNext->pPrev = pBucket->pPrev;
				pBucket->pPrev = NULL;
				pBucket->pNext = m_pFirstEmpty;
				pBucket->pKey = NULL;
				m_pFirstEmpty->pPrev = pBucket;
				m_pFirstEmpty = pBucket;
			}
			else
			{
				// It's a landlord
				if(pBucket->pNext)
				{
					// Move the next renter into the landlord bucket
					struct HashBucket* pOldBucket = pBucket->pNext;
					pBucket->pNext = pOldBucket->pNext;
					pBucket->pKey = pOldBucket->pKey;
					pBucket->pValue = pOldBucket->pValue;
					if(pBucket->pNext)
						pBucket->pNext->pPrev = pBucket;

					// Delete the former-renter's old bucket
					pOldBucket->pNext = m_pFirstEmpty;
					pOldBucket->pPrev = NULL;
					pOldBucket->pKey = NULL;
					m_pFirstEmpty->pPrev = pOldBucket;
					m_pFirstEmpty = pOldBucket;
				}
				else
				{
					// Just delete the landlord bucket
					pBucket->pNext = m_pFirstEmpty;
					pBucket->pKey = NULL;
					m_pFirstEmpty->pPrev = pBucket;
					m_pFirstEmpty = pBucket;
				}
			}
			m_nCount--;
			m_nModCount++;
			return;
		}
	}
}

#ifndef NO_TEST_CODE

#define TEST_HASH_TABLE_ELEMENTS 32000

bool VerifyBucketCount(GHashTableBase* pHT)
{
	GHashTableEnumerator hte(pHT);
	void* pValue;
	int n = 0;
	while(hte.GetNext(&pValue))
		n++;
	if(n != pHT->GetCount())
		return false;
	return true;
}

/*static*/ void GHashTable::Test()
{
	int nElements = TEST_HASH_TABLE_ELEMENTS;
	GHashTable ht(13);
	int* pNothing = new int[nElements];
	ArrayHolder<int*> hNothing(pNothing);
	int n;
	for(n = 0; n < nElements; n++)
		ht.Add(&pNothing[n], (const void*)&pNothing[n]);
	for(n = 0; n < nElements; n += 7)
		ht.Remove(&pNothing[n]);
	if(!VerifyBucketCount(&ht))
		ThrowError("failed");
	void* pVal = NULL;
	for(n = 0; n < nElements; n++)
	{
		if(n % 7 == 0)
		{
			if(ht.Get(&pNothing[n], &pVal))
				ThrowError("failed");
		}
		else
		{
			if(!ht.Get(&pNothing[n], &pVal))
				ThrowError("failed");
			if(pVal != &pNothing[n])
				ThrowError("failed");
		}
	}
}
#endif // !NO_TEST_CODE

// ------------------------------------------------------------------------------

const char* GHashTableEnumerator::GetNext(void** ppValue)
{
	if(m_pHashTable->GetModCount() != m_nModCount)
		ThrowError("The HashTable was modified since this enumerator was constructed!");
	const void* pValue;
	while(m_nPos < m_pHashTable->m_nBucketCount)
	{
		const char* pKey = m_pHashTable->m_pBuckets[m_nPos].pKey;
		pValue = m_pHashTable->m_pBuckets[m_nPos].pValue;
		m_nPos++;
		if(pKey)
		{
			*ppValue = (void*)pValue;
			return pKey;
		}
	}
	return NULL;
}

void* GHashTableEnumerator::GetCurrentValue()
{
	if(m_nPos <= 0)
		return NULL;
	return (void*)m_pHashTable->m_pBuckets[m_nPos - 1].pValue;
}

// ------------------------------------------------------------------------------

bool GConstStringHashTable::Get(const char* pKey, int nLen, void** ppOutValue)
{
	GTEMPBUF(char, szKey, nLen + 1);
	memcpy(szKey, pKey, nLen);
	szKey[nLen] = '\0';
	return Get(szKey, ppOutValue);
}

bool GConstStringToIntsHashTable::Get(const char* pKey, int nLen, int* pValue)
{
	GTEMPBUF(char, szKey, nLen + 1);
	memcpy(szKey, pKey, nLen);
	szKey[nLen] = '\0';
	return Get(szKey, pValue);
}
